{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Swap Nodes in Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: swapPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两两交换链表中的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg\" style=\"width: 422px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4]\n",
    "<strong>输出：</strong>[2,1,4,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目在范围 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [swap-nodes-in-pairs](https://leetcode.cn/problems/swap-nodes-in-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [swap-nodes-in-pairs](https://leetcode.cn/problems/swap-nodes-in-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        '''\n",
    "        recursion: return new head \n",
    "        \n",
    "        remember the one after ng, temp\n",
    "        reverse pointer -> ng.next = pre\n",
    "        linked to the rest reversed part -> pg.next = swapPairs(temp)\n",
    "        '''\n",
    "        if not head:\n",
    "            return \n",
    "        if not head.next:\n",
    "            return head\n",
    "        preHead = head\n",
    "        newHead = head.next\n",
    "        \n",
    "        temp = newHead.next # 3\n",
    "        newHead.next = preHead # 2->1\n",
    "        preHead.next = self.swapPairs(temp)\n",
    "        return newHead\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head):\n",
    "        pre ,pre.next = ListNode(0),head\n",
    "        dummy = pre\n",
    "        while pre.next and pre.next.next:\n",
    "            a = pre.next\n",
    "            b = a.next\n",
    "            pre.next,b.next,a.next = b,a,b.next\n",
    "            pre = a\n",
    "        return dummy.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: 'ListNode') -> 'ListNode':\n",
    "        dummy = pre = ListNode(0)\n",
    "        pre.next = head\n",
    "        while pre.next and pre.next.next:\n",
    "            a = pre.next\n",
    "            b = a.next\n",
    "            pre.next, b.next, a.next = b, a, b.next\n",
    "            pre = a\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        # if not head or not head.next:\n",
    "        #     return head\n",
    "        p=ListNode(0)\n",
    "        p.next = head\n",
    "        one,two= p,head\n",
    "        \n",
    "        while two and two.next: \n",
    "            print(two.val)\n",
    "            three = two.next\n",
    "            four = three.next\n",
    "    \n",
    "            one.next = three\n",
    "            three.next = two\n",
    "            two.next = None\n",
    "            one = two\n",
    "            two = four\n",
    "        one.next = two\n",
    "            \n",
    "        return p.next\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        pre, pre.next = self, head\n",
    "        while pre.next and pre.next.next:\n",
    "            a,b=pre.next,pre.next.next\n",
    "            a.next=b.next\n",
    "            pre.next,pre.next.next=b,a\n",
    "            pre=a\n",
    "        return self.next\n",
    "            \n",
    "            \n",
    "        \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        rel = head.next\n",
    "        p = head\n",
    "        while p!=None:\n",
    "            \n",
    "            if p.next == None:\n",
    "                break\n",
    "            if p.next!=None and p.next.next == None:\n",
    "                p1 = p.next\n",
    "                p1.next = p\n",
    "                p.next = None\n",
    "                break\n",
    "            if p.next != None and p.next.next != None and p.next.next.next == None:\n",
    "                p1 = p.next\n",
    "                p2 = p.next.next\n",
    "                p1.next = p\n",
    "                p.next = p2\n",
    "                p2.next = None\n",
    "                break\n",
    "            \n",
    "            p1 = p.next\n",
    "            p2 = p.next.next\n",
    "            p3 = p.next.next.next\n",
    "            p1.next = p\n",
    "            p.next = p3\n",
    "            p = p2\n",
    "            \n",
    "        return rel\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: 'ListNode') -> 'ListNode':\n",
    "        pre, pre.next = self, head\n",
    "        while pre.next and pre.next.next:\n",
    "            a = pre.next\n",
    "            b = a.next\n",
    "            pre.next = b\n",
    "            a.next = b.next\n",
    "            b.next = a\n",
    "            pre = a\n",
    "        return self.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: 'ListNode') -> 'ListNode':\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        new_head = head.next\n",
    "        head.next = self.swapPairs(head.next.next)\n",
    "        new_head.next = head\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        if not head: return \n",
    "        point = head\n",
    "        head = point.next if point.next is not None else head\n",
    "        last = ListNode(-1)\n",
    "        while point and point.next:\n",
    "            temp = point.next\n",
    "            point.next = temp.next\n",
    "            temp.next = point\n",
    "            last.next = temp\n",
    "            last = point\n",
    "            point = point.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head):\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        \n",
    "        prev_node = dummy\n",
    "        \n",
    "        while head and head.next:\n",
    "            first_node = head\n",
    "            second_node = head.next\n",
    "            \n",
    "            prev_node.next = second_node\n",
    "            first_node.next = second_node.next\n",
    "            second_node.next = first_node\n",
    "            \n",
    "            prev_node = first_node\n",
    "            head = first_node.next\n",
    "            \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        #返回的是交换后的链表头结点  head:是将要交换的结点\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        firsthead=head\n",
    "        secondhead=head.next\n",
    "        #swapping\n",
    "        firsthead.next=self.swapPairs(secondhead.next)#fir.next是指下一次交换后的结点\n",
    "        secondhead.next=firsthead\n",
    "        return secondhead\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "            \n",
    "        N = head.next\n",
    "        head.next = self.swapPairs(N.next)\n",
    "        N.next = head\n",
    "        return N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "        用官方题解的 方法2 迭代版本实现\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return\n",
    "        res = ListNode(None)\n",
    "        res.next= head\n",
    "        tmp = res\n",
    "        while True:\n",
    "            if (not tmp.next) or (not tmp.next.next):\n",
    "                break\n",
    "            n1 = tmp.next\n",
    "            n2 = tmp.next.next\n",
    "            # 交换前为 tmp > n1 > n2\n",
    "            # 交换后为 tmp > n2 > n1\n",
    "            tmp.next = n2\n",
    "            n1.next = n2.next\n",
    "            n2.next = n1\n",
    "\n",
    "            # 然后让tmp指向 n1, 进行下一轮迭代\n",
    "            # 注意: 这里tmp=tmp.next是错的, 必须是tmp=n1\n",
    "            tmp = n1\n",
    "            \n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        curr = head\n",
    "        f_head = ListNode()\n",
    "        prev = f_head\n",
    "        if head:\n",
    "            if head.next:\n",
    "                while curr and curr.next:\n",
    "                    temp1 = curr.next\n",
    "                    temp2 = curr.next.next\n",
    "                    prev.next = temp1\n",
    "                    curr.next = temp2\n",
    "                    temp1.next = curr\n",
    "                    prev = curr\n",
    "                    curr = temp2\n",
    "            else:\n",
    "                f_head.next = curr\n",
    "        return f_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=24 lang=python3\r\n",
    "#\r\n",
    "# [24] 两两交换链表中的节点\r\n",
    "#\r\n",
    "# https://leetcode-cn.com/problems/swap-nodes-in-pairs/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Medium (66.70%)\r\n",
    "# Likes:    758\r\n",
    "# Dislikes: 0\r\n",
    "# Total Accepted:    201.6K\r\n",
    "# Total Submissions: 293.7K\r\n",
    "# Testcase Example:  '[1,2,3,4]'\r\n",
    "#\r\n",
    "# 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。\r\n",
    "#\r\n",
    "# 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。\r\n",
    "#\r\n",
    "#\r\n",
    "#\r\n",
    "# 示例 1：\r\n",
    "#\r\n",
    "#\r\n",
    "# 输入：head = [1,2,3,4]\r\n",
    "# 输出：[2,1,4,3]\r\n",
    "#\r\n",
    "#\r\n",
    "# 示例 2：\r\n",
    "#\r\n",
    "#\r\n",
    "# 输入：head = []\r\n",
    "# 输出：[]\r\n",
    "#\r\n",
    "#\r\n",
    "# 示例 3：\r\n",
    "#\r\n",
    "#\r\n",
    "# 输入：head = [1]\r\n",
    "# 输出：[1]\r\n",
    "#\r\n",
    "#\r\n",
    "#\r\n",
    "#\r\n",
    "# 提示：\r\n",
    "#\r\n",
    "#\r\n",
    "# 链表中节点的数目在范围 [0, 100] 内\r\n",
    "# 0\r\n",
    "#\r\n",
    "#\r\n",
    "#\r\n",
    "\r\n",
    "# @lc code=start\r\n",
    "# Definition for singly-linked list.\r\n",
    "\r\n",
    "\r\n",
    "class ListNode:\r\n",
    "    def __init__(self, val=0, next=None):\r\n",
    "        self.val = val\r\n",
    "        self.next = next\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\r\n",
    "        if not head:\r\n",
    "            return head\r\n",
    "        if head.next != None:\r\n",
    "            result = head.next\r\n",
    "        else:\r\n",
    "            result = head\r\n",
    "        flag = 1\r\n",
    "        exchange = None\r\n",
    "        while head.next != None:\r\n",
    "            flag = flag+1\r\n",
    "            if flag % 2 == 0:\r\n",
    "                first = head\r\n",
    "                last = head.next\r\n",
    "                head = last\r\n",
    "                first.next = last.next\r\n",
    "                head.next = first\r\n",
    "                if exchange != None:\r\n",
    "                    exchange.next = head\r\n",
    "                exchange = head.next\r\n",
    "            head = head.next\r\n",
    "        return result\r\n",
    "\r\n",
    "\r\n",
    "if __name__ == \"__main__\":\r\n",
    "    node1 = ListNode()\r\n",
    "    node1.val = 1\r\n",
    "    node1.next = ListNode()\r\n",
    "    node1.next.val = 2\r\n",
    "    node1.next.next = ListNode()\r\n",
    "    node1.next.next.val = 3\r\n",
    "    node1.next.next.next = ListNode()\r\n",
    "    node1.next.next.next.val = 4\r\n",
    "    node1.next.next.next.next = None\r\n",
    "    so = Solution()\r\n",
    "    so.swapPairs(node1)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\r\n",
    "        if not head or not head.next:\r\n",
    "            return head\r\n",
    "        newHead = head.next\r\n",
    "        head.next = self.swapPairs(newHead.next)\r\n",
    "        newHead.next = head\r\n",
    "\r\n",
    "        return newHead\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def print_l(self, head):\n",
    "        while head:\n",
    "            print(head.val)\n",
    "            head = head.next\n",
    "        print('fin')\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur and cur.next :\n",
    "            tmp_next = cur.next\n",
    "            if not pre:\n",
    "                pre = tmp_next\n",
    "                head = tmp_next\n",
    "            else:\n",
    "                pre.next = tmp_next\n",
    "            \n",
    "            cur.next = cur.next.next\n",
    "            tmp_next.next = cur\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            self.print_l(head)\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        elif not head.next:\n",
    "            return head\n",
    "        \n",
    "        firstnode = head\n",
    "        secondnode = head.next\n",
    "        phead = copy.deepcopy(secondnode)\n",
    "        ret = phead\n",
    "\n",
    "        while (1):\n",
    "            phead.next = copy.deepcopy(firstnode)\n",
    "            phead = phead.next\n",
    "\n",
    "            firstnode = secondnode.next \n",
    "            if firstnode != None:\n",
    "                secondnode = firstnode.next\n",
    "                if secondnode != None:\n",
    "                    phead.next = copy.deepcopy(secondnode)\n",
    "                    phead = phead.next\n",
    "                else:\n",
    "                    phead.next = copy.deepcopy(firstnode)\n",
    "                    break\n",
    "            else:\n",
    "                phead.next = None\n",
    "                break\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        cur=ListNode()\n",
    "        cur.next=head\n",
    "        first=head.next\n",
    "        while cur.next and cur.next.next:\n",
    "            temp=cur.next\n",
    "            cur.next=cur.next.next\n",
    "            temp.next=cur.next.next\n",
    "            cur.next.next=temp\n",
    "            cur=temp\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        elif head.next is None:\n",
    "            return head\n",
    "        preNode=ListNode(val=None)\n",
    "        preNode.next=head\n",
    "        start=preNode\n",
    "        nextNode=head.next\n",
    "        lastNode=nextNode.next\n",
    "        while head and nextNode:\n",
    "            if lastNode is None or lastNode.next is None:\n",
    "                midNode=nextNode\n",
    "                nextNode=head\n",
    "                head=midNode\n",
    "                preNode.next=head\n",
    "                head.next=nextNode\n",
    "                nextNode.next=lastNode\n",
    "                break\n",
    "            else:\n",
    "                midNode=nextNode\n",
    "                nextNode=head\n",
    "                head=midNode\n",
    "                preNode.next=head\n",
    "                head.next=nextNode\n",
    "                nextNode.next=lastNode\n",
    "                preNode=nextNode\n",
    "                head=lastNode\n",
    "                nextNode=lastNode.next\n",
    "                lastNode=nextNode.next          \n",
    "        return start.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        tmp = dummy\n",
    "        while tmp.next and tmp.next.next:\n",
    "            node1 = tmp.next\n",
    "            node2 = tmp.next.next\n",
    "            tmp.next = node2\n",
    "            node1.next = node2.next\n",
    "            node2.next = node1\n",
    "            tmp = node1\n",
    "        return dummy.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0, head)\n",
    "        cur = dummy\n",
    "        while cur.next and cur.next.next:\n",
    "            tmp1 = cur.next\n",
    "            tmp2 = cur.next.next.next\n",
    "            cur.next = cur.next.next\n",
    "            cur.next.next = tmp1\n",
    "            cur.next.next.next = tmp2\n",
    "            cur = cur.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return None\n",
    "        left = ListNode(next=head)\n",
    "        right = head.next\n",
    "        head = left\n",
    "        while right:\n",
    "            left.next.next = right.next\n",
    "            right.next = left.next\n",
    "            left.next = right\n",
    "            print(head)\n",
    "            left = right.next\n",
    "            if right.next == None or right.next.next == None:\n",
    "                break\n",
    "            else:\n",
    "                right = right.next.next.next\n",
    "        \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        p = head\n",
    "        lst = []\n",
    "        while p:\n",
    "            lst.append(p)\n",
    "            p = p.next\n",
    "        if len(lst) == 1:\n",
    "            return head\n",
    "        orl = len(lst)\n",
    "        l = len(lst) - len(lst) % 2\n",
    "        print(lst, l)\n",
    "        last = None\n",
    "        \n",
    "        for i in range(0, l, 2):\n",
    "            \n",
    "            print(i)\n",
    "            a, b = lst[i], lst[i + 1]\n",
    "            if last:\n",
    "               last.next = b\n",
    "            b.next = a\n",
    "            last = a\n",
    "            \n",
    "        if orl % 2 == 0:\n",
    "            lst[-2].next = None\n",
    "        else:\n",
    "            last.next = lst[-1]\n",
    "            lst[-1].next = None\n",
    "        return lst[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0, head)\n",
    "        p = dummy\n",
    "        while p and p.next and p.next.next:\n",
    "            t = p.next\n",
    "            p.next = t.next\n",
    "            t.next = p.next.next\n",
    "            p.next.next = t\n",
    "            p = t\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy_head = ListNode(next=head)\n",
    "        cur = dummy_head\n",
    "        while cur.next and cur.next.next:\n",
    "            temp = cur.next\n",
    "            temp1 = cur.next.next.next\n",
    "            cur.next = cur.next.next\n",
    "            cur.next.next = temp\n",
    "            temp.next = temp1\n",
    "            cur = cur.next.next\n",
    "        return dummy_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dum = ListNode(next=head)\n",
    "        cur = dum\n",
    "        while cur.next and cur.next.next:\n",
    "            t1, t2 = cur.next, cur.next.next.next\n",
    "            cur.next = cur.next.next\n",
    "            cur.next.next = t1\n",
    "            t1.next = t2\n",
    "            cur = cur.next.next\n",
    "        return dum.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
